#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    bool dfs(int u, int c, vector<vector<int>>& graph, vector<bool>& st, vector<int>& col) {
        if (st[u] && col[u] != c) {
            return false;
        }
        if (!st[u]) {
            col[u] = c;
            st[u] = true;
        }
        for (auto k : graph[u]) {
            if (st[k] && col[k] == 3 - c) {
                continue;
            }
            else if (st[k] && col[k] == c)return false;
            if (!dfs(k, 3 - c, graph, st, col)) {
                return false;
            }
        }
        return true;
    }
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<bool>st(n, false);
        vector<int> col(n);
        for (int i = 0; i < n; i++) {
            if (!st[i]) {
                if (!dfs(i, 1, graph, st, col)) {
                    // cout<<i<<endl;
                   //  for(int k=0;k<n;k++)cout<<col[k]<<endl;
                    return false;
                }
            }
        }
        return true;
    }
};